[Leetcode单排] 单词搜索 (N79 N212)

backtracking dfs search

字数统计: 1k阅读时长: 5 min

 2019/07/30  Share

79. Word Search

https://leetcode-cn.com/problems/word-search/

在二维数组中搜索具体的单词是否存在。这个题目有几个值得借鉴吸收的地方：

1、当要在二维数组的特定点四周继续寻找时，不需要写函数计算这个点周围有几个可用点，可以直接在递归中判断是否 out of range；

2、要注意递归函数的具体功能含义。初始尝试时，找到开始点和递归方法写成了两个函数，实际上可以融合；

3、下面的做法没有采用单独的列表存储走过的元素，而是采用将值记录为0，这样就可以在递归中碰到这个点时必然不相等，就相当于排除了这个点。

public boolean exist(char[][] board, String word) {
    for (int i = 0; i < board[0].length; i++) {
        for (int j = 0; j < board.length; j++) {
            if (dfs(i, j, 0, word, board)) {
                return true;
            }
        }
    }
    return false;
}

private boolean dfs(int x, int y, int i, String word, char[][] board) {
    if (x < 0 || y < 0 || x >= board[0].length || y >= board.length) {
        return false;
    }
    if (board[y][x] != word.charAt(i)) {
        return false;
    }
    if (i == word.length() - 1) {
        return true;
    }
    char temp = board[y][x];
    board[y][x] = '0';
    boolean res = dfs(x + 1, y, i + 1, word, board)
            || dfs(x - 1, y, i + 1, word, board)
            || dfs(x, y + 1, i + 1, word, board)
            || dfs(x, y - 1, i + 1, word, board);
    board[y][x] = temp;
    return res;
}

下面这个是使用了访问变量的版本：

public boolean exist(char[][] board, String word) {
    boolean[][] visit = new boolean[board.length][];
    for (int i = 0; i < board.length; i++) {
        visit[i] = new boolean[board[0].length];
    }
    for (int i = 0; i < board[0].length; i++) {
        for (int j = 0; j < board.length; j++) {
            if (dfs(i, j, 0, word, board, visit)) {
                return true;
            }
        }
    }
    return false;
}

private boolean dfs(int x, int y, int i, String word, char[][] board, boolean[][] visit) {
    if (x < 0 || y < 0 || x >= board[0].length || y >= board.length) {
        return false;
    }
    if (board[y][x] != word.charAt(i) || visit[y][x]) {
        return false;
    }
    if (i == word.length() - 1) {
        return true;
    }
    visit[y][x] = true;
    boolean res = dfs(x + 1, y, i + 1, word, board, visit)
            || dfs(x - 1, y, i + 1, word, board, visit)
            || dfs(x, y + 1, i + 1, word, board, visit)
            || dfs(x, y - 1, i + 1, word, board, visit);
    visit[y][x] = false;
    return res;
}

212. Word Search II

https://leetcode.com/problems/word-search-ii/

与上题不同的是，这次是给一个字符串数组，结果是所有满足条件的字符串的集合，其实就是把上题中的单字符串换成字符串数组。如果基于上文中的解法直接加一层for循环：Your runtime beats 13.43 %, memory usage beats 90.76 %。

正确做法是基于 Trie 树，其实从一串字符串中进行筛选就应该想到使用前缀树。答案借鉴的这位的做法，这代码风格和我上一题基本一模一样。实际上需要以二维数组的每个字符去匹配 Trie 树，从顶向下找，看能包含几个字符串。

// 构建Trie树节点(26叉树)
class TrieNode {
    public TrieNode[] children = new TrieNode[26];
    public String word = null;
}

// 构建Trie树
class Trie {
    public TrieNode root = new TrieNode();
		
  	// 只需要插入方法即可
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); ++i) {
            int charNo = word.charAt(i) - 'a';
            if (node.children[charNo] == null) {
                node.children[charNo] = new TrieNode();
            }
            node = node.children[charNo];
        }
        node.word = word;
    }
}

public class Solution {

    public List<String> findWords(char[][] board, String[] words) {
        // 事先构造
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }

        boolean[][] visited = new boolean[board.length][board[0].length];
        Set<String> resultSet = new HashSet<>();

        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[0].length; ++j) {
                search(board, visited, i, j, board.length, board[0].length, trie.root, resultSet);
            }
        }
        return new ArrayList<>(resultSet);
    }

    private void search(char[][] board, boolean[][] visit, int i, int j, int x, int y, TrieNode node, Set<String> result) {
        if (i < 0 || j < 0 || i >= x || j >= y || visit[i][j]) {
            return;
        }
        node = node.children[board[i][j] - 'a'];
        if (node == null) {
            return;
        }
        if (node.word != null) {
            result.add(node.word);
            // 此处没有 return，后续可能还存在字符串
        }

        visit[i][j] = true;
        search(board, visit, i - 1, j, x, y, node, result);
        search(board, visit, i + 1, j, x, y, node, result);
        search(board, visit, i, j - 1, x, y, node, result);
        search(board, visit, i, j + 1, x, y, node, result);
        visit[i][j] = false;
    }
}

Next Post

Clojure in Action: Clojure 构件
Previous Post

Clojure in Action: 程序结构、程序流程

CATALOG

1. 79. Word Search
2. 212. Word Search II

